Developer CD Series 1998 November: Tool Chest/Dev.CD Nov 98 TC.toast/Sample Code/Snippets/Development Tools & Languages/DTSCPlusLibrary/Sources/CollectionClasses.cp

Text File | 1993-01-14 | 17.0 KB | 599 lines | [TEXT/MPS ]

/* _________________________________________________________________________________________________________ //
  Copyright © 1992-93 Apple Computer, Inc. All rights reserved.
  Macintosh Developer Technical Support.C++ Macintosh Toolbox Framework.
  Programmer: Kent Sandvik
  Date: 11/7/92
  Revision comments are at the end of this file.
  ---
  The following collection classes are implemented: TLinkedList, TStack, (TQueue, TDeQueue),
  THashTable.
  CollectionClasses.cp contains the collection class member functions.
  _________________________________________________________________________________________________________ */

#ifndef _COLLECTION_
#include "CollectionClasses.h"
#endif


// _________________________________________________________________________________________________________ //
//    TLINKEDLIST Class definitions.

//    CONSTRUCTORS AND DESTRUCTORS
#pragma segment Collections
TLinkedList::TLinkedList(short max)
// Create a Linked list class (max entries pre-defined in a constant in the header file).
{
    fMaxCollectionSize = max;                    // keep track of how many entries we could add to the collection
    fCollectionSize = 0;                        // no entries yet
    // Fix the head and the rest of the pointer hooks.
    fHead = new fNODE;                            // create nodes
    fTail = new fNODE;
    fLastEntry = new fNODE;
    fCurrentNode = new fNODE;

    fHead->fNext = fTail;                        // default head points at tail, then we will push in nodes between
    fHead->fPrevious = fHead;                    // bit your own tail
    fTail->fNext = fTail;                        // bite your own tail
    fTail->fPrevious = fHead;                    // hook tail with head (double linked list)
    fTail->fKey = NULL;                            // mark the last entry as NULL
    fHead->fKey = NULL;                            // mark the first entry as NULL
    fLastEntry->fPrevious = fHead;                // hook the ptr node between the head
    fLastEntry->fNext = fTail;                    // …and the tail
}


#pragma segment Collections
TLinkedList::~TLinkedList()
// Destruct the structures required for the former linked list.
{
    struct fNODE* temp = fHead;                    // create a temp node

    while (temp != fTail)
        // while we have entries, delete them from head to tail
        {
            fHead = temp;                        // copy temp node to the head position
            temp = temp->fNext;                    // and make temp point at the next one
            delete fHead;                        // meanwhile delete the head, and continue copying tmp to head
        }
}


//    MAIN INTERFACES

#pragma segment Collections
Boolean TLinkedList::Append(const TItemtype item)
// Append entry to the linked list (at the end).
{
    if (fCollectionSize < fMaxCollectionSize)
    {
        struct fNODE*        temp = new fNODE;    // create a new node
        temp->fKey = item;

        // Hook the temp node between the last entry and the tail
        if (fCollectionSize == 0)                // first entry?
        {
            fHead->fNext = temp;                // hook it just after the head
            temp->fNext = fTail;                // and before the tail
            fLastEntry = temp;                    // and keep track of it!
        }
        else                                    // OK now we will track of the fCurrentNode
            {
                temp->fNext = fTail;            // stuck it just before the tail
                fLastEntry->fNext = temp;        // and after the current node
                fLastEntry = temp;                // and mark it the current node
            }

        fCollectionSize++;                        // keep a count on the size of the linked list
        goto AppendOK;
    }
    ASSERT(fCollectionSize < fMaxCollectionSize, "\pOverflow of the LinkedList");
    return false;
AppendOK:return true;
}


#pragma segment Collections
Boolean TLinkedList::Remove(const TItemtype item)
// Remove defined entry from the linked list.
{
    // First find the item, if found remove it, connect the links and decrease the collection size count
    this->Reset();                                // get back to the first entry
    struct fNODE*            temp = fHead;        // keep a temp pointer to earlier node passed

    do                                            // walk along the list
    {
        if (fCurrentNode->fKey == item)            // found a hit?
        {
            // yes!
            temp->fNext = fCurrentNode->fNext;    // short circuit the current node
            delete fCurrentNode;                // delete this node
            fCollectionSize--;                    // decreate the collection count
            goto OK;                            // and jump out
        }

        temp = fCurrentNode;                    // keep track of the just visited node
        fCurrentNode = fCurrentNode->fNext;        // …and step forward
    } while (fCurrentNode != fTail);            // as long as we are inside the linked list

    return false;                                // nothing happened…
OK:    return true;                                // OK, we were able to delete the entry
}


#pragma segment Collections
Boolean TLinkedList::IsEmpty()
// Check if the collection is empty (head points at tail).
{
    return (fHead->fNext == fTail);                // check if the next pointer is pointing on the tail
}


#pragma segment Collections
Boolean TLinkedList::Find(const TItemtype item)
// Find if we have the itemtype in the 'queue'.
{
    TItemtype tempVal;
    this->Reset();                                // get back to the first entry

    while ((tempVal = this->Next()) != NULL)
        // get all entries one at a time
        {
            if (tempVal == item)                // if we found a one-to-one relationship
                return true;                    // signal OK
        }
    return false;                                // otherwise signal false
}


#pragma segment Collections
Size TLinkedList::GetSize() const
// Return the internal count of entries in collection.
{
    return fCollectionSize;
}


// ITERATORS
#pragma segment Collections
TItemtype TLinkedList::First()
// Get the first entry in the collection.
{
    if (fCollectionSize != 0)
        return fHead->fNext->fKey;                // return what FHead->fNext has (the first 'real' node)
    else
        return NULL;
}


#pragma segment Collections
TItemtype TLinkedList::Next()
// Return next entry in the list.
{
    TItemtype item;
    item = fCurrentNode->fKey;                    // get current item
    fCurrentNode = fCurrentNode->fNext;            // then increase the node to the next entry

    return item;                                // return item
}


#pragma segment Collections
TItemtype TLinkedList::Last()
// Return last entry in the list.
{
    // because we cached the first entry, it's easy to return it
    // we might have problems with a real de-queue later if
    // we don't revise this scheme (but most likely we will override Last() with new behavior
    return fLastEntry->fKey;                    // the fLastNode is always pointing at the last entry
}


#pragma segment Collections
void TLinkedList::Reset()
// Make the current node point at the first entry from beginning (reset).
{
    fCurrentNode = fHead->fNext;                // reset the fCurrentNode pointer to the first entry
}


// _________________________________________________________________________________________________________ //
//    TSTACK Class definitions.

//    CONSTRUCTORS AND DESTRUCTORS
#pragma segment Collections
TStack::TStack(short max)
// Create a stack class (max pre-defined in the header files as a constant).
{
    fMaxCollectionSize = max;                    // keep track of how big we could grow the stack into
    fCollectionSize = 0;                        // no entries yet
}


#pragma segment Collections
TStack::~TStack()
// Default constructor -- not used for the time being.
{
}


//    MAIN INTERFACES
#pragma segment Collections
Boolean TStack::Push(const TItemtype item)
// Push entry into the stack (beginning).
{
    if (fCollectionSize < fMaxCollectionSize)    // yes, we bail out and don't add more entries
    {
        struct fNODE* temp = new fNODE;            // create temp node
        temp->fKey = item;                        // store value in temp node
        temp->fNext = fHead->fNext;                // make temp point at the real next block
        fHead->fNext = temp;                    // and make temp suddenly the real head (stack head!)
        fCollectionSize++;                        // increase the stack size
        if (fCollectionSize == 1)                // first entry?
            fLastEntry = temp;                    // store it for fast access later (cache the ptr)

        goto PushOK;
    }
    ASSERT(fCollectionSize < fMaxCollectionSize, "\pOverflow of the Stack");// signal about a possible problem
    return false;
PushOK:return true;
}


#pragma segment Collections
TItemtype TStack::Pop()
// Pop entry from the stack (beginning).
{
    TItemtype item;
    struct fNODE* temp = fHead->fNext;            // create temp node with the header next pointer values
    fHead->fNext = temp->fNext;                    // copy back the following pointer from temp to the head
    item = temp->fKey;                            // get the temp item

    delete temp;                                // delete the suddenly non-needed node
    fCollectionSize--;                            // decrease the stack
    return item;                                // return the asked value
}


#pragma segment Collections
Boolean TStack::Append(const TItemtype item)
// Append entry, same as Push, but we included it.
{
    return (this->Push(item));                    // call the one and only method supported with stack insertion
}


#pragma segment Collections
Boolean TStack::Remove(const TItemtype            /*item*/)
// Remove is not implemented, but we had to include it because we are subclassing from a TLinkedList.
{
    return false;                                // not supported
}


// _________________________________________________________________________________________________________ //
//    TQUEUE
//    CONSTRUCTORS AND DESTRUCTORS
#pragma segment Collections
TQueue::TQueue(short max)
// Create a queue class (max pre-defined in the header files as a constant).
{
    fMaxCollectionSize = max;                    // keep track of how big we could grow the stack into
    fCollectionSize = 0;                        // no entries yet
}


#pragma segment Collections
TQueue::~TQueue()
// Default destructor, not used for the time being.
{
}


//    MAIN INTERFACE
#pragma segment Collections
Boolean TQueue::Put(const TItemtype item)
// Put entry into the queue (beginning).
{
    if (fCollectionSize < fMaxCollectionSize)    // no problems?
    {
        struct fNODE* temp = new fNODE;            // create a new node
        temp->fKey = item;                        // add value to the node bucket

        // place it in the beginning of the queue
        temp->fNext = fHead->fNext;                // push it into the queue
        fHead->fNext = temp;                    // now it's there

        // update the tail pointer
        if (fCollectionSize == 0)                // first entry?
        {
            fTail->fPrevious = temp;            // hook fTail to the entry
        }
        temp->fPrevious = fHead;                // and hook it back to head
        fLastEntry->fPrevious = temp;            // and as well as to the current first entry
        fLastEntry = temp;                        // and mark it as the current first entry

        fCollectionSize++;                        // increase the collection count
        goto QueueOK;
    }
    ASSERT(fCollectionSize < fMaxCollectionSize, "\pOverflow of TQueue");
    return false;
QueueOK:return true;
}


#pragma segment Collections
Boolean TQueue::Append(const TItemtype item)
// Append is the same as Put.
{
    return (this->Put(item));                    // call TQueue.Put
}


#pragma segment Collections
TItemtype TQueue::Get()
// Get entry from the end of the list (queue).
{
    TItemtype item;

    // get the node and the value
    struct fNODE* temp = fTail->fPrevious;        // get the last before fTail
    item = temp->fKey;                            // get the item


    // change the pointers
    fTail->fPrevious = temp->fPrevious;            // hook fTail to the previous entry
    temp->fPrevious->fNext = fTail;                // hook the node to tail as well

    delete temp;                                // delete the entry

    fCollectionSize--;                            // decrease the collection count
    return item;                                // return the item
}


#pragma segment Collections
TItemtype TQueue::Last()
// Get last entry from queue.
{
    return fTail->fPrevious->fKey;                // get the last entry
}


#pragma segment Collections
Boolean TQueue::Remove(const TItemtype            /*item*/)
// Remove is not supported, but we needed to include this because TQueue is subclassed from TLinkedList
{
    return false;                                // not supported
}



// _________________________________________________________________________________________________________ //
// TDEQUE

//    CONSTRUCTORS AND DESTRUCTORS
#pragma segment Collections
TDeque::TDeque(short max)
// Create dequeue class (max pre-defined in the header files as a constant).
{
    fMaxCollectionSize = max;                    // keep track of how big we could grow the stack into
    fCollectionSize = 0;                        // no entries yet
}


#pragma segment Collections
TDeque::~TDeque()
// Default destructor, not used for the time being.
{
}

#pragma segment Collections
Boolean TDeque::Push(const TItemtype item)
// Push entry into queue (beginning).
{
    return (TQueue::Put(item));                    // call inherited Put
}


#pragma segment Collections
Boolean TDeque::PutAtEnd(const TItemtype item)
// Place entry at end of the deque.
{
    if (fCollectionSize < fMaxCollectionSize)    // bail out if we reach the limit
    {
        struct fNODE*     temp = new fNODE;        // create temp node
        temp->fKey = item;                        // store the value
        temp->fNext = fTail;                    // point at tail
        temp->fPrevious = fTail->fPrevious;        // make the backwards ptr hooked to the new entry
        fTail->fPrevious->fNext = temp;            // and hook the old last one into this one
        fTail->fPrevious = temp;                // make the tail point at the new entry

        fCollectionSize++;                        // increase the counter
        goto PutAtEndOK;
    }
    ASSERT(fCollectionSize < fMaxCollectionSize, "\pOverflow of the TDeque");
    return false;
PutAtEndOK:return true;
}


#pragma segment Collections
TItemtype TDeque::Pop()
// Pop entry from the queue end.
{
    TItemtype item;
    struct fNODE* temp = fHead->fNext;            // hook to the beginning of the deque
    fHead->fNext = temp->fNext;                    // hook head to the following node
    temp->fNext->fPrevious = fHead;                // and the next one should point back at the head

    item = temp->fKey;                            // get the stored value
    delete temp;                                // remove node
    fCollectionSize--;                            // decrease the counter

    return item;                                // and return the item
}


// _________________________________________________________________________________________________________ //
// THASHTABLE

//    CONSTRUCTORS AND DESTRUCTORS
#pragma Collections
THashTable::THashTable()
// Create a hash table class.
{
    // Clear the array bucket.
    for (long i = 0; i < NBUCKETS; i++)
        fBucket[i] = 0;
}


#pragma Collections
THashTable::~THashTable()
// Delete any memory structures required for the hashtable class.
{
    // Delete the entries in the array bucket.
    for (long i = 0; i < NBUCKETS; i++)
    {
        THashEntryPtr p = fBucket[i];            // get a ptr to the entry
        while (p)
            // while a valid ptr
            {
                fBucket[i] = p->fNext;            // install next entry in array
                delete p;                        // delete the current node
                p = fBucket[i];                    // ptr back to the new value
            }
    }
}


//    MAIN INTERFACE
#pragma segment Collections
Boolean THashTable::Add(THashKey key,
                        TItemtype value)
// Add entries to the hash table.
{
    THashEntryPtr p;
    THashKey whichItem = this->Hash(key);        // hash out the real value

    cout << " whichItem = " << whichItem << "\n";

    p = FindInBucket(fBucket[whichItem], key);
    if (p)                                        // have already an entry?
        goto problem;                            // signal the failure

    p = this->AddElement(key);                    // add our entry
    p->fValue = value;                            // add the item value to the entry
    return true;

problem:return false;
}


#pragma segment Collections
Boolean THashTable::Remove(THashKey key)
// Remove entries from the hash table.
{
    THashKey whichItem = this->Hash(key);        // hash out the real value
    THashEntryPtr p = FindInBucket(fBucket[whichItem], key);
    if (!p)                                        // no valid ptr?
        goto problem;

    if (fBucket[whichItem] == p)
        fBucket[whichItem] = p->fNext;            // connect to next node

    delete p;                                    // delete current node
    return true;

problem:return false;
}



#pragma segment Collections
TItemtype THashTable::Find(THashKey key)
// Find entries in the hash table.
{
    THashKey whichItem = this->Hash(key);        // hash out the real value
    THashEntryPtr p = this->FindInBucket(fBucket[whichItem], key);
    if (!p)
        return 0;                                // return 0
    else
        return p->fValue;                        // return valid value
}


#pragma segment Collections
void THashTable::MapCar(MapFun function)
// Run a function on each entry in the hash table.
{
    for (long i = 0; i < NBUCKETS; i++)            // iterate through all the entries
    {
        THashEntryPtr p = fBucket[i];            // get the ptr to the entry

        while (p)
            // while we have a nice value
            {
                function(p);                    // call the function on p
                p = p->fNext;                    // get the next ptr
            }
    }
}


// PRIVATE INTERNAL FUNCTIONS
#pragma Collection
THashEntryPtr THashTable::AddElement(THashKey key)
// Add an element to the internal structure.
{
    THashKey whichItem = this->Hash(key);
    THashEntryPtr p = new THashEntry(key);

    p->fNext = fBucket[whichItem];                // get ptr to next entry
    if (fBucket[whichItem])                        // OK?
        fBucket[whichItem]->fPrevious = p;        // establish ptrs backwards

    fBucket[whichItem] = p;                        // as well as the current one

    return p;
}


#pragma Collections
THashKey THashTable::Hash(THashKey key)
// Hash out a key to be used with the buckets. Override for your own preferences.
{
    key &= kResourceIDMask;
    return ((THashKey)(0x7FF & (key ^ (key >> 11))) % NBUCKETS);
    // Note: if you write your own hash function, don't forget modula NBUCKETS to get
    // down the size of the key so it hooks to the buckets.
}


#pragma Collections
THashEntryPtr THashTable::FindInBucket(THashEntryPtr p,
                                       THashKey key)
// Find bucket where entry is located.
{
    while (p)
        // valid pointer?
        {
            if (p->fKey == key)                    // hit?
                break;                            // found it!
            p = p->fNext;                        // nope, continue cycling the list
        }
    return p;                                    // return found (not found) ptr
}


// _________________________________________________________________________________________________________ //


/*    Change History (most recent last):
  No        Init.    Date        Comment
  1            khs        11/7/92        New file
  2            khs        11/28/92    Added TLinkedList
  3            khs        11/29/92    Added TQueue and TDeque
  4            khs        1/14/93        Cleanup
*/